package com.fzkj.search;

import java.util.Arrays;

/**
 * 折半查找/二分查找
 * @author yaya
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,3,6,32,34,122,632,711,988,1000,2233,4564,12345,12346,12347,13245};
        System.out.println(binarySearch2(arr, 13245));
    }

    /**
     * 不靠谱，哒咩
     * @param arr 目标数组
     * @param des 目标元素
     * @return 元素值
     */
    private static int binarySearch(int[] arr, int des){
        int middle = arr.length >> 1; // /2
        if (des == arr[middle]){
            return arr[middle];
        }
        if (middle == 0){  // middle == 0, 且 des != arr[middle], 说明数组只有一个元素且不等于待查找元素，返回-1表示未找到
            return -1;
        }
        if (des < arr[middle]){
            return binarySearch(Arrays.copyOfRange(arr, 0, middle), des);
        }else {
            return binarySearch(Arrays.copyOfRange(arr, middle + 1, arr.length), des);
        }
    }

    /**
     * 查找元素下标
     */
    private static int binarySearch2(int[] arr, int des){
        int low = 0, high = arr.length - 1;
        while (low <= high){
            int mid = (low + high) >> 1;
            if (des == arr[mid]){
                return mid;
            } else if (des > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
